deuxieme qui renvoie le deuxième élément d’une liste.(*
contrat fonction deuxième
description: fonction qui retourne le deuxième élément d'une liste
paramètres: la liste ('a liste) qui doit contenir au moins 2 éléments
résultat: un élément de type a, le deuxième de la liste
profil: 'a liste -> 'a
*)
let deuxième liste =
match liste with
| [] | [_] -> failwith "liste vide"
| _::b::_ -> b
let deuxième liste =
match liste with
| _::b::_ -> b;;
| _ -> failwith "liste vide"
let%test _ = deuxieme [3;4] = 4
let%test _ = deuxieme ['a';'b';'c';'d'] = 'b'
n_a_zero et zero_a_n, telles que : n_a_zero n = [n; n-1;...; 1 ; 0] et zero_a_n n = [0; 1 ;...; n-1; n](*
Contrat n_a_zero : int -> int list - Retourne la liste [n;n-1;...;0]
Paramètres :
n : int - un entier positif
Résultat : int list - liste bien formée
*)
let rec n_a_zero n =
if n < 0 then failwith "n doit être positif" else
if n = 0 then
[0]
else
n::n_a_zero (n-1)
let%test _ = n_a_zero 0 = [0]
let%test _ = n_a_zero 1 = [1;0]
let%test _ = n_a_zero 2 = [2;1;0]
(*
Contrat zero_a_n : int -> int list - Retourne la liste [0;1;...;n]
Paramètres :
n : int - un entier positif
Résultat : int list - liste bien formée
*)
let zero_a_n n =
let rec aux_zan p liste =
if p < 0 then
liste
else
aux_zan (p-1) (p::liste)
in aux_zan n []
let%test _ = zero_a_n 0 = [0]
let%test _ = zero_a_n 1 = [0;1]
let%test _ = zero_a_n 2 = [0;1;2]
Attention : utilisation de append interdite.
3. Liste des indices/positions d’un élément e dans une liste l.
(*
Contrat positions : 'a -> 'a list '-> int list - retourne une liste des positions d'un élément dans une liste
Paramètres : une liste quelconque et un élément
Résultat : une liste d'entier qui correspond aux positions
*)
let positions e l =
let rec aux_positions l ind liste_ind =
match l with
| [] -> liste_ind
| t::q -> (
if t = e then
aux_positions q (ind+1) (ind::liste_ind)
else
aux_positions q (ind+1) liste_ind
)
in aux_positions l 0 []
let%test _ = positions [] = []
let%test _ = positions ['a';'a';'b';'a'] = [3;1;0]
let%test _ = positions [1;2;3;2;1] = [3;1]
Utilisation des itérateurs obligatoire.
map, qui applique une fonction donnée à tous les éléments d’une liste, i.e. map f [a;b;c] = [f a;f b;f c].(*
Contrat map : ('a -> 'b) -> 'a list -> 'b list - Retourne la liste en entrée à laquelle la même fonction a été appliquée à tous les éléments
Paramètres :
f : 'a -> 'b - fonction qui va être appliquée sur tous les éléments de la liste
l : 'a list
Résultat : 'b list - La liste à laquelle f a été appliquée sur tous les éléments
*)
let map f l = List.fold_right (fun t mapq -> (f t)::mapq) l []
let%test _ = map (fun x -> x+1) [0; 1; 2] = [1;2;3]
flatten (aplatissement d’une liste de listes).(*
Contrat flatten : 'a list list -> 'a list - Calcule l'applatissement d'une liste
Paramètres :
l : 'a list list
Résultat : 'a list - L'applatissement de la liste l
*)
let flatten l = List.fold_right (fun t flattenq -> t@flattenq) l []
let%test _ = flatten [[]] = []
let%test _ = flatten [[[]]] = [[]]
let%test _ = flatten [[1;2];[3;4]] = [1;2;3;4]
fsts qui prend une liste de couples et renvoie la liste des premiers éléments.(*
Contrat fsts : ('a * 'b) list -> 'a list - Calcule la liste des premiers éléments de la liste de couples
Paramètres :
l : ('a * 'b) list - liste des couples
Résultat : 'a list - Liste des premiers éléments des couples de l
*)
let fsts l = List.map (fun (e,_) -> e) l
(* ou avec une fonction partielle *)
let fsts = List.map (fun (e,_) -> e)
let%test _ = fsts [] = []
let%test _ = fsts [('a','b')] = ['a']
let%test _ = fsts [(1,'a');(2,'b');(3,'c')] = [1;2;3]
split telle que : split [(a1,b1);...;(an,bn)] = ([a1;...;an],[b1;...;bn]).(*
Contrat split : ('a * 'b) list -> ('a list * 'b list) - Sépare la liste en deux dans un couple avec les premiers éléments d'un côté, les seconds éléments de l'autre
Paramètres :
l : 'a list - liste à séparer en deux
Résultat : ('a list * 'b list)
*)
let split l = List.fold_right (fun (e1,e2) (r1,r2) -> (e1::r,e2::r2)) l ([],[])
let%test _ = split [] = []
let%test _ = split [(1,2)] = ([1],[2])
let%test _ = split [(1,'a');(2,'b');(3,'c')] = ([1;2;3],['a';'b';'c'])
(*
Contrat supprimer_doublons : 'a list -> 'a list - Calcule une liste sans doublons
Paramètres :
l : 'a list - La liste à laquelle on va supprimer les doublons
Résultat : l sans doublons
*)
let supprimer_doublons l = List.fold_right (fun t suppq -> if (List.mem t suppq) then suppq else t::suppq) l []
let%test _ = supprimer_doublons [] = []
let%test _ = supprimer_doublons [1;2;3;4] = [1;2;3;4]
let%test _ = supprimer_doublons [1;2;1;5;6;1;8] = [1;2;5;6;8]
Dans une spécification, on trouve plutôt des déclarations de types que des définitions. On parle alors de types privés ou types abstraits. L’absence de définition de types interdit à l’utilisateur de manipuler les valeurs “à la main” et n’importe comment, l’obligeant donc à employer les fonctions de manipulation fournies.
Si, en plus des déclarations de types et de fonctions, on trouve des équations qui spécifient la sémantique de ces fonctions (sans faire apparaître une implantation particulière), on parle alors de types abstraits algébriques. Bien sûr, ces équations ne sont pas supportées par les langages de programmation.
(* ensemble.mli *)
(****** Type abstrait = pas de definition *****)
type 'a set
(***** CONSTRUCTEURS *****)
(* Fonction vide : construit l'ensemble vide *)
val vide : unit -> 'a set
(*
Fonction singleton : constuit un ensemble a un élément
Paramètre : a l'élément
Retour : l'ensemble {a}
*)
val singleton : 'a -> 'a set
(*
Fonction union : réalise l'union de deux ensembles
Paramètres : ens1 et ens2 deux ensembles
Retour : l'union ensembliste de ens1 et ens2
*)
val union : 'a set -> 'a set -> 'a set
(***** ACCESSEURS *****)
(* Fonction est_vide : teste si un ensemble est vide *)
val est_vide : 'a set -> bool
(*
Fonction choix : choisi un élément de l'ensemble
Précondition : l'ensemble ne doit pas être vide
*)
val choix : 'a set -> 'a
(* Fonction appartient : teste si un élément est dans l'ensemble *)
val appartient : 'a -> 'a set -> bool
(***** DESTRUCTEURS *****)
(*
Fonction enleve : retire un élément à l'ensemble
Paramètres : e l'élément à enlever, ens l'ensemble
Retour : ens\{e}
*)
val enleve : 'a -> 'a set -> 'a set
(*
Fonction intersection : réalise l'intersection de deux ensembles
Paramètres : ens1 et ens2 deux ensembles
Retour : l'intersection ensembliste de ens1 et ens2
*)
val intersection : 'a set -> 'a set -> 'a set
Les constructeurs “abstraits” jouent exactement le même rôle que de véritables constructeurs, sauf qu’ils ne montrent rien de l’implantation (ce sont juste des fonctions).
S’il fallait en faire un TAA, on aurait par exemple les propriétés suivantes :
est_vide (vide ()) = true
not (appartient x (vide ())) = true
appartient x (singleton y) = (x = y)
appartient x (union ens ens') = appartient x ens || appartient x ens'
...
(* ensemble.ml *)
(* Définition du type 'a set *)
type 'a set = 'a list
(* CONSTRUCTEURS *)
let vide () = []
let singleton e = [e]
let rec union ens1 ens2 =
List.fold_right (fun t tq -> if (List.mem t ens2) then tq else t::tq) ens1 ens2
(* ACCESSEURS *)
let est_vide ens = (ens=[])
let choix ens =
match ens with
| [] -> failwith "Ensemble vide!";
| t::q ->t
let appartient = List.mem
(* DESTRUCTEURS *)
let rec enleve e ens =
match ens with
| [] -> []
| t::q -> if e=t then q else t::(enleve e q)
let rec intersection ens1 ens2 =
List.fold_right (fun t tq -> if (appartient t ens2) then t::tq else tq) ens1 []
La file est une structure de données linéaire qu’on retrouve partout. On peut enfiler des éléments à une extrémité et les retirer à l’autre extrémité, comme un pipe-line où circulerait un “flot” de valeurs. La file est une structure de type FIFO (first in, first out).
(* Définition du type *)
type 'a file
(* CONSTRUCTEURS *)
val vide : unit -> 'a file
val enfiler : 'a -> 'a file -> 'a file
(* ACESSEURS *)
val est_vide : 'a file -> bool
(* DESTRUCTEURS *)
val defiler : 'a file -> 'a * 'a file
(* Définition du type *)
type 'a file = 'a list
(* CONSTRUCTEURS *)
let vide () = []
let enfiler e f = f@[e] (* complexité linéaire, bof bof quoi *)
(* ACESSEURS *)
let est_vide f = f = []
(* DESTRUCTEURS *)
let defiler f =
match f with
| [] -> failwith "Erreur: la file est vide"
| e::r -> (e,r)
O(n) majoritairement.
On a déjà vu la complexité moyenne et du pire cas, qui s’intéressent seulement à une exécution donnée d’un algorithme. La complexité amortie permet de lisser les temps de calcul des différents appels à un algorithme, supposé inséré dans une application plus grosse. C’est une moyenne temporelle sur toutes ses exécutions. Cette mesure est donc plus fiable quant au temps réel passé dans un algorithme donné. Cela permet de prouver par exemple que quelques exécutions de mauvaise complexité (du pire cas) peuvent être compensées à la longue par d’autres exécutions plus favorables.
(* Définition du type *)
type 'a file = 'a list * 'a list
(* CONSTRUCTEURS *)
let vide () = ([],[])
let enfiler e f = f@[e] (* complexité linéaire, bof bof quoi *)
(* ACESSEURS *)
let est_vide f = f = ([],[])
(* DESTRUCTEURS *)
let defiler (deb,fin_inv) =
match fin_inv with
| e::r -> (e,(deb,r))
| [] -> (
match List.rev deb with
| [] -> failwith "Erreur: la file est vide"
| e::r -> (e,([],r))
)